class Matrix:
    """docstring for Matrix"""

    def __init__(self, elem: list):
        check = [len(item) for item in elem]
        if set(check) == {0}:
            self.elem = []
            self.row = 0
            self.col = 0
        elif len(set(check)) == 1:
            self.elem = elem
            self.row = len(elem)
            self.col = len(elem[0])
        elif len(set(check)) > 1:
            raise ValueError("The column of each row is not equal")

    def __repr__(self):
        mat = ""
        for item in self.elem:
            mat += str(item)
            mat += '\n'
        return str(mat)

    def __iter__(self):
        return iter(self.elem)

    def __add__(self, other):
        if (self.row != other.row) or (self.col != other.col):
            raise TypeError("The two matrix's shape is not equal")
        else:
            new = [[i + j for i, j in zip(A, B)] \
                   for A, B in zip(self.elem, other.elem)]
            return Matrix(new)

    def __mul__(self, other):
        if self.col != other.row:
            raise TypeError("The first column must be equal to the second row")
        else:
            # 采用列表推导式的办法生成矩阵
            # 采用[[0] * other.col ] * self.row)]只是复制了第一个元素 self.row 遍，都是指向同一个内存地址
            new = [[0] * other.col for i in range(self.row)]
            for i in range(self.row):
                for j in range(other.col):
                    for k in range(self.col):
                        new[i][j] += self.elem[i][k] * other.elem[k][j]
            return Matrix(new)

    def __sub__(self, other):
        if (self.row != other.row) or (self.col != other.col):
            raise TypeError("The two matrix's shape is not equal")
        else:
            new = [[i - j for i, j in zip(A, B)] \
                   for A, B in zip(self.elem, other.elem)]
            return Matrix(new)

    def __neg__(self):
        new = [[-i for i in ele] for ele in self.elem]
        return Matrix(new)

    def __pow__(self, power, modulo=None):
        # quick pow
        if not self.is_square():
            raise TypeError("The matrix is not square matrix")
        else:
            new = eyes(self.row)
            A = Matrix(self.elem)
            while power:
                if power & 1:
                    new = new * A
                power >>= 1
                A = A * A
            return new

    def shape(self):
        # 获得矩阵形状
        print((self.row, self.col))

    def is_square(self):
        # 判断是否是方阵
        return self.row == self.col

    def getitem(self, i: int, j: int):
        # 获得矩阵第 (i, j) 个位置的元素
        i -= 1
        j -= 1
        if (i < 0) or (i > self.row) or (j < 0) or (j > self.col):
            raise IndexError("list index out of range")
        else:
            return self.elem[i][j]

    def setitem(self, i: int, j: int, value) -> None:
        # 修改矩阵第 (i, j) 个位置的元素
        i -= 1
        j -= 1
        if (i < 0) or (i > self.row) or (j < 0) or (j > self.col):
            raise IndexError("list index out of range")
        else:
            self.elem[i][j] = value

    def T(self):
        # Transposition
        new = [[0] * self.row for i in range(self.col)]
        for i in range(self.row):
            for j in range(self.col):
                new[j][i] = self.elem[i][j]
        return Matrix(new)

    def tiling(self):
        new = [[x for y in self.elem for x in y]]
        return Matrix(new)


def zeros(row: int, col: int) -> Matrix:
    new = [[0] * col for i in range(row)]
    return Matrix(new)


def eyes(n: int) -> Matrix:
    new = [[0] * n for i in range(n)]
    for i in range(n):
        new[i][i] = 1
    return Matrix(new)


def ones(row: int, col: int) -> Matrix:
    new = [[1] * col for i in range(row)]
    return Matrix(new)
